package com.example.myletcodelearing.chaintable

/**
 * @author tgw
 * @date 2022/11/3
 * @describe
 */
class ListNode(var value: Int?) {
    var next: ListNode? = null;
}

fun main(array: Array<String>) {
//    val link = MyLinkedList1()
//    link.addAtHead(4)
//    link.addAtIndex(1,5)
//    link.addAtIndex(2,1,)
//    link.addAtIndex(3,9)
////    link.addAtHead(1)
////    link.addAtHead(9)
//    link.print()

//    println("值反转：")
//    println("斐波那契额：${link.fbnq(5)}")
//    val linkReverse = MyLinkedList1.Solution()
//    link.head = linkReverse.reverseList(link.head)!!
//    link.print()
//    println("值删除：")
//    link.deleteAtValue(1)
//    println("值删除倒数开始：")
//    link.head = link.deleteAtLink(1)
//    link.head = link.deleteAtLink2(0)
//
    println("值结合开始：")
    val link = MyLinkedList1()
    link.addAtHead(1)
    link.addAtIndex(1, 2)
    link.addAtIndex(2, 3)
    link.addAtIndex(3, 4)
    link.addAtIndex(4, 5)

    val link2 = MyLinkedList1()
    link2.addAtHead(2)
    link2.addAtIndex(1, 4)
    link2.addAtIndex(2, 6)


    link.print()
//    link2.print()

//    link.head = link.combineLink(link.head, link2.head)
//    link.head = link.mergeTwoLists(link.head, link2.head)
//    link.head = link.mergeTwoLists2(link.head, link2.head)
    link.head = link.removeNthFromEnd(link.head?.next,2)
    println("值：removeNthFromEnd")
    link.print()

}

class MyLinkedList1() {

    fun print() {
        var next: ListNode? = head
        while (next != null) {
            println("值：${next.value}")
            next = next.next
        }
    }

    /**
     * 初始化
     */

    var head: ListNode? = ListNode(0)
    var size: Int = 0

    /**
     * 获取指定位置的元素，找不到返回 -1
     */
    fun get(index: Int): Int {
        val k = index
        if (k < 0 || k >= size) return -1
        // 因为将伪头作为头结点，所以需要 +1 才是当前查找元素所在的结点
        var cur: ListNode? = head
        for (i in 0 until (k + 1)) cur = cur?.next

        return cur?.value ?: -1
    }

    /**
     * 在头部添加元素
     */
    fun addAtHead(`val`: Int) {
        addAtIndex(0, `val`)
    }

    /**
     * 在尾部添加元素
     */
    fun addAtTail(`val`: Int) {
        addAtIndex(size, `val`)
    }

    /**
     * 在指定位置插入元素
     */
    fun addAtIndex(index: Int, `val`: Int) {
        var k = index
        if (k > size) return
        if (k < 0) k = 0

        // 因为有伪头结点存在，所以 i < index 找到的节点，一定是插入位置的前驱节点
        var pre: ListNode? = head
        for (i in 0 until k) pre = pre?.next

        val node = ListNode(`val`)
        node.next = pre?.next
        pre?.next = node
        size++
    }

    /**
     * 删除指定位置的元素
     */
    fun deleteAtIndex(index: Int) {
        var k = index
        if (k < 0 || k >= size) return
        // 因为有伪头结点存在，所以 i < index 找到的节点，一定是插入位置的前驱节点
        var pre: ListNode? = head
        for (i in 0 until k) pre = pre?.next

        pre?.next = pre?.next?.next
        size--
    }

    /**
     * 删除元素
     */
    fun deleteAtValue(value: Int): ListNode? {

        // 因为有伪头结点存在，所以 i < index 找到的节点，一定是插入位置的前驱节点
        var pre: ListNode? = head
        if (pre?.value == value) {
            return pre.next
        }

        while (pre?.next != null) {
            if (pre.next!!.value == value) {
                pre.next = pre.next?.next
                return head
            } else {
                pre = pre.next
            }
        }
        return pre
    }


    /**
     *输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
     * 例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。
    示例：
    给定一个链表: 1->2->3->4->5, 和 k = 2.
    返回链表 4->5.

    初始化快慢指针，指向链表的头结点
    让快指针 fast 沿着链表移动 k 次，此时 fast 指向第 k 个节点
    循环遍历链表，当 fast.next == null 结束循环
    移动慢指针 slow = slow.next
    移动快指针 fast = fast.next
    当循环结束时，即慢指针 slow 指向的是倒数第 k 个节点，返回 slow
     */
    fun deleteAtLink(index: Int): ListNode? {
        var fast: ListNode? = head
        var slow: ListNode? = head
        //利用快指针得出偏移项
        (0 until index).forEach { _ ->
            fast = fast?.next
        }
        //利用快指针不为空证明还有值
        while (fast != null) {
            fast = fast?.next
            //利用慢指针，代表两者间差异距离
            slow = slow?.next
        }
        return slow
    }

    fun deleteAtLink2(index2: Int): ListNode? {
        var index1 = index2
        var index = 0
        var fast: ListNode? = head
        var slow: ListNode? = head
        var size = 0
        while (fast != null) {
            fast = fast.next
            //利用慢指针，代表两者间差异距离
            size++
        }
        if (index2 > size) {
            index1 = size
        }
        while (slow != null) {
            //利用慢指针，代表两者间差异距离
            if (index == size - index1) {
                break
            }
            slow = slow.next
            index++
        }

        return slow
    }

//    fun combineLink(head1: ListNode?, head2: ListNode?): ListNode? {
//        var cur: ListNode? = ListNode(0)
//        var head: ListNode? = cur
//        var l1: ListNode? = head1
//        var l2: ListNode? = head2
//        while (l1 != null && l2 != null) {
//            if (l1.value > l2.value) {
//                var l2next = l2.next
//                var l1next = l1
//                l2.next = l1next
//                cur?.next = l2
//                l2 = l2next
//            }else{
//                var l1next = l1.next
//                var l2next = l2
//                l1.next = l2next
//                cur?.next = l1
//                l1 = l1next
//            }
//            cur = cur?.next
//        }
//
//        return head?.next
//    }


//    fun mergeTwoLists(l1: ListNode?, l2: ListNode?): ListNode? {
//        var head: ListNode? = ListNode(0)
//        var cur: ListNode? = head
//        var pl1: ListNode? = l1;
//        var pl2: ListNode? = l2;
//        while (pl1 != null && pl2 != null) {
//            if (pl1.value < pl2.value) {
//                cur?.next = pl1
//                pl1 = pl1.next
//            } else {
//                cur?.next = pl2
//                pl2 = pl2.next
//
//            }
//            cur = cur?.next
//        }
//
//        cur?.next = if (pl1 == null) pl2 else pl1
//        return head?.next
//    }

    fun mergeTwoLists2(l1: ListNode?, l2: ListNode?): ListNode? {
        var head:ListNode?=ListNode(0)
        var cur = head
        var pl1 = l1
        var pl2 = l2
        while (pl1 != null && pl2 !=null){
            if (pl1.value!!<pl2.value!!){
                cur?.next =pl1
                pl1 = pl1.next
            }else{
                cur?.next =pl2
                pl2 = pl2.next
            }
            cur = cur?.next
        }
        cur?.next = if (pl1 == null) pl2 else pl1
        return head?.next
    }

    /**给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
     *
     * 输入：head = [1,2,3,4,5], n = 2
    输出：[1,2,3,5]

     * */
    fun removeNthFromEnd(head: ListNode?, n: Int): ListNode? {
        var newNode = head
        var sizeNum = 0
        while (newNode != null){
            sizeNum++
            newNode = newNode.next
        }

        var newNode1:ListNode? = ListNode(0)
        newNode1?.next = head
        var newNode2 = newNode1
        var head = head

        while (head != null){
            if (sizeNum ==n){
                newNode2?.next  = head.next
                head = head.next
                sizeNum --
                continue
            }
            //将当前对象指向它的next ，这样下次操作的就是next，一步步的操作它的引用
            newNode2 = newNode2?.next
            head = head.next
            sizeNum --
        }
        return newNode1?.next
    }

    fun removeNthFromEnd2(head: ListNode?, n: Int): ListNode? {
        var n = n
        val pre = ListNode(0)
        pre.next = head
        var start: ListNode? = pre
        var end: ListNode? = pre
        while (n != 0) {
            start = start!!.next
            n--
        }
        while (start!!.next != null) {
            start = start.next
            end = end!!.next
        }
        end!!.next = end.next!!.next
        return pre.next
    }



    class Solution {

        fun reverseList(head: ListNode?): ListNode? {
            var pre: ListNode? = null
            var current = head
            while (current != null) {
                val next = current.next
                current.next = pre
                pre = current
                current = next
            }
            return pre;
        }

    }

    fun fbnq(n: Int): Int {
        if (n <= 1) {
            return 1
        }
        return fbnq(n - 1) + fbnq(n - 2)
    }

}
